package 栈;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Author: biubiu0002
 * @Date: 2021-09-12 15:21
 **/
public class 有效的括号字符串 {
    public static void main(String[] args) {
        System.out.println(new 有效的括号字符串().checkValidString("((((()(()()()*()(((((*)()*(**(())))))(())()())(((())())())))))))(((((())*)))()))(()((*()*(*)))(*)()"));

    }

    public boolean checkValidString(String s) {
        //两个栈 分别放 ( 和 * 出现的下标
        int n = s.length();
        Deque<Integer> a =new ArrayDeque();
        Deque<Integer> b =new ArrayDeque();
        for(int i=0;i<n;i++){
            char c = s.charAt(i);
            if(c=='('){
                a.push(i);
            }
            else if(c=='*'){
                b.push(i);
            }
            else if(c==')'){
                //0 0
                if(a.isEmpty()&&b.isEmpty()){
                    return false;
                }
                //10 11
                if(!a.isEmpty()){
                    a.pop();
                }
                //0 1
                else{
                    b.pop();
                }
            }
        }
        while(!a.isEmpty()&&!b.isEmpty()){
            if(a.peekLast()<b.peekLast()){
                a.pop();
                b.pop();
            }else{
                return false;
            }
        }
        if(a.isEmpty()){
            return true;
        }
        else{
            return false;
        }

    }
}
